package sort.advanced_sort;

import java.util.Arrays;

public class Demo7_HeapSort_Down {
    /**
     * 降序排列的堆排序
     */
    public static void downAdjust(int[] arr, int parentIndex, int size) {
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < size) {
            if (childIndex + 1 < size && arr[childIndex + 1] < arr[childIndex]) {
                childIndex++;
            }
            if (arr[parentIndex] <= arr[childIndex]) {
                break;
            }
            swap(arr, parentIndex, childIndex);
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
    }

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //1.构建最小堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));
        //2.循环删除堆顶
        for(int i = arr.length - 1; i > 0; i--){
            swap(arr, i, 0);
            downAdjust(arr, 0, i);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {7,5,8,1,2,4,6,3,10};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
